package main

import (
	"fmt"
	"go-study/algorithm/common"
)

// 如何计算两个单链表所代表的数之和，个位数在链表头

func main() {
	head1 := &common.LNode{}
	head2 := &common.LNode{}

	common.CreateNode3(head1, head2)

	fmt.Println("Head1：", head1)
	fmt.Println("Head2：", head2)

	head := add(head1, head2)

	fmt.Println("相加后：", head)
}

func add(head1, head2 *common.LNode) *common.LNode {
	if head1 == nil || head1.Next == nil {
		return head2
	}

	if head2 == nil || head2.Next == nil {
		return head1
	}

	// 相加之后的链表头
	resultHead := &common.LNode{}

	// 记录进位和两个节点的加和
	var c, sum int

	current1 := head1.Next
	current2 := head2.Next
	current := resultHead

	for current1 != nil && current2 != nil {
		sum = current1.Data + current2.Data + c
		current.Next = &common.LNode{
			Data: sum % 10,
		}
		c = sum / 10

		current = current.Next
		current1 = current1.Next
		current2 = current2.Next
	}

	if current1 == nil {
		for current2 != nil {
			sum = current2.Data + c
			current.Next = &common.LNode{
				Data: sum % 10,
			}
			c = sum / 10

			current = current.Next
			current2 = current2.Next
		}
	}

	if current2 == nil {
		for current1 != nil {
			sum = current1.Data + c
			current.Next = &common.LNode{
				Data: sum % 10,
			}
			c = sum / 10

			current = current.Next
			current1 = current1.Next
		}
	}

	if c == 1 {
		current.Next = &common.LNode{
			Data: 1,
		}
	}

	return resultHead
}
